package programmercarl.二叉树.C18;

import java.util.HashMap;
import java.util.Map;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }
public class Solution {

    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return findTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode findTree(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return null;
        }
        int currVal=postorder[postEnd-1];
        //建立节点
        TreeNode root=new TreeNode(currVal);
        //找到中序遍历位置
        int rootIndex = map.get(currVal);
        int leftLen=rootIndex-inBegin;
        root.left = findTree(inorder, inBegin, rootIndex, postorder, postBegin, postBegin +leftLen);//左闭右开，已经建立的节点不要了
        root.right = findTree(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftLen, postEnd-1);
        return root;
    }
}
